package Review;

import java.util.ArrayList;
import java.util.Iterator;


public class Test25 {

	public static void main(String[] args) {
		BinaryTreeNode node1=new BinaryTreeNode(10);
		BinaryTreeNode node2=new BinaryTreeNode(5);
		BinaryTreeNode node3=new BinaryTreeNode(12);
		BinaryTreeNode node4=new BinaryTreeNode(4);
		BinaryTreeNode node5=new BinaryTreeNode(7);		
		node1.left=node2;
		node1.right=node3;
		node2.left=node4;
		node2.right=node5;
		node3.left=node3.right=null;
		node4.left=node4.right=null;
		node5.left=node5.right=null;		
		findPath(node1,22);
	}
    public static void findPath(BinaryTreeNode root,int target){
    	if(root==null){
    		return;
    	}
    	ArrayList<Integer> array = new ArrayList<Integer>();
    	findPath(root, array,0,target);
    }
    public static void findPath(BinaryTreeNode root,ArrayList<Integer> array,int sum,int target){
    	array.add(root.value);
    	sum += root.value;
    	if(root.left==null&&root.right==null&&sum==target){
    		System.out.print("�ҵ�·��:");
    		Iterator<Integer> it = array.iterator(); 
    		while(it.hasNext()){
    			System.out.print(it.next());
    			System.out.print(" ");
    		}
    	}
	
    	if(root.left!=null){
    		findPath(root.left, array, sum, target);
    	}
    	if(root.right!=null){
    		findPath(root.right, array, sum, target);
    	}
    	sum-=root.value;
    	array.remove(array.size()-1);
    	
    }
    
}
